//
// Description: 221. 最大正方形
// Created by Loading on 2022/4/8.
//

#include <bits/stdc++.h>

using namespace std;

int maximalSquare(vector<vector<char>> &matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    // dp[i][j] 表示以点(i,j)为右下角的正方形最大边长
    vector<vector<int>> dp(m, vector<int>(n));

    int side = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == '1') {
                if (!i || !j) {
                    // 边界条件
                    dp[i][j] = 1;
                } else {
                    // 当前位置最大边长取决于其左侧，左上侧，上侧三个位置
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
                side = max(dp[i][j], side);
            }
        }
    }

    return side * side;
}

int main() {
    vector<vector<char>> matrix{{'0', '0', '0', '1'},
                                {'1', '1', '0', '1'},
                                {'1', '1', '1', '1'},
                                {'0', '1', '1', '1'},
                                {'0', '1', '1', '1'}};
    int res = maximalSquare(matrix);
    cout << res << endl;

    return 0;
}